package main

import "fmt"

func mergesort(arr []int, l int, r int) {
	if l >= r {
		return
	}
	mid := l + (r-l)/2
	mergesort(arr, l, mid)
	mergesort(arr, mid+1, r)
	if arr[mid] > arr[mid+1] {
		merge(arr, l, mid, r)
	}
}

func merge(arr []int, l int, mid int, r int) {
	aux := make([]int, r-l+1)
	for i := l; i <= r; i++ {
		aux[i-l] = arr[i]
	}
	i, j := l, mid+1
	for k := l; k <= r; k++ {
		if i > mid {
			arr[k] = aux[j-l]
			j++
		} else if j > r {
			arr[k] = aux[i-l]
			i++
		} else if aux[i-l] <= aux[j-l] {
			arr[k] = aux[i-l]
			i++
		} else {
			arr[k] = aux[j-l]
			j++
		}
	}

}

func main() {
	arr := []int{3, 5, 6, 9, 1, 6, 0, 25, 13}
	mergesort(arr, 0, len(arr)-1)
	fmt.Println(arr)
}
